package com.yitau.sort;

import com.yitau.utils.ArrayUtils;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 快速排序
 */
public class QuickSort {

    /**
     * 快速排序递归实现
     * 1. 从数列中挑出一个元素作为基准，这里选取最后一个
     * 2. 分区（partition）：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
     * 3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序（数据量大可能会造成堆栈溢出：StackOverflowError）
     * @param array 原数组，执行完后数组内容改变
     * @param begin 需要排序数组的起始位置
     * @param end 需要排序数组的结束位置
     */
    public static void quickSort(int[] array, int begin, int end) {
        if (begin < end) {
            int pivot = partition(array, begin, end);
            quickSort(array, begin, pivot - 1);
            quickSort(array, pivot + 1, end);
        }
    }

    /**
     * 快速排序递归实现（尾递归优化）
     * 1. 从数列中挑出一个元素作为基准，这里选取最后一个
     * 2. 分区（partition）：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
     * 3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序（数据量大可能会造成堆栈溢出：StackOverflowError）
     * @param array 原数组，执行完后数组内容改变
     * @param begin 需要排序数组的起始位置
     * @param end 需要排序数组的结束位置
     */
    public static void quickSort2(int[] array, int begin, int end) {
        while (begin < end) {
            int pivot = partition(array, begin, end);
            quickSort(array, begin, pivot - 1);
            begin = pivot + 1;
        }
    }

    /**
     * 快速排序非递归实现
     * 1. 从数列中挑出一个元素作为基准，这里选取最后一个
     * 2. 分区（partition）：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
     * 3. 把分区之后两个区间的边界压入栈保存，并循环 1、2 步骤
     * @param array 原数组，执行完后数组内容改变
     */
    public static void quickSort3(int[] array) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(0);
        stack.push(array.length - 1);
        while (!stack.isEmpty()) {
            // 出栈后进行划分操作
            int end = stack.pop();
            int begin = stack.pop();
            int pivot = partition(array, begin, end);
            // 划分结束后保存两个子区间的边界值
            if (pivot > begin) {
                stack.push(begin);
                stack.push(pivot - 1);
            }
            if (pivot < end) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    /**
     * 将数组以基准划分，小于其的放前面，大于其的放后面
     * @param array 原数组，执行完后数组内容改变
     * @param begin 需要划分数组的起始位置
     * @param end 需要划分数组的结束位置
     * @return pivot 返回基准位置
     */
    public static int partition(int[] array, int begin, int end) {
        // 默认基准为最后一个值
        int pivot = array[end];
        int i = begin;
        int j = end;
        while (i < j) {
            // 从左往右找到第一个大于 pivot 的或遇到 j
            while (i < j && array[i] <= pivot) {
                i++;
            }
            // 从右往左找到第一个小于 pivot 的或遇到 i
            while (i < j && array[j] >= pivot) {
                j--;
            }
            // 交换 i,j 位置
            ArrayUtils.swap(array, i, j);
        }
        // 交换 pivot 和 i 的位置
        // i 经过前面的交换已经是大于 pivot 的值或者 pivot
        ArrayUtils.swap(array, i, end);
        return i;
    }

    public static void quickSort(int[] array) {
        System.out.print("排序前：");
        ArrayUtils.printArray(array);
        long startTime = System.currentTimeMillis();
//        quickSort(array, 0, array.length - 1);
//        quickSort2(array, 0, array.length - 1);
        quickSort3(array);
        long endTime = System.currentTimeMillis();
        float excTime = (float) (endTime-startTime) / 1000;
        System.out.print("排序后：");
        ArrayUtils.printArray(array);
        System.out.println("执行时间为：" + excTime + "s");
    }

    public static void main(String[] args) {
        // write your code here
        System.out.println("正序：");
        quickSort(ArrayUtils.DEFAULT_ARRAY_ASC);
        System.out.println("逆序：");
        quickSort(ArrayUtils.DEFAULT_ARRAY_DESC);
        System.out.println("随机：");
        quickSort(ArrayUtils.DEFAULT_ARRAY_RANDOM);
    }
}
